In recent years, for attacks to cryptographic modules implemented in software or hardware, various malicious deciphering methods have been conceived to decipher data of the encryption key without authorization, through an analysis of intermediate data generated during execution of the encryption employing some sort of techniques. For example, in order to attack cryptographic modules implemented in software, using a development tool such as a debugger, an attacker can extract the intermediate data of the encryption execution directly from a register where the data is temporarily stored. Therefore, based on the extracted intermediate data, the encryption key data can be analyzed. Further malicious deciphering methods, such as Simple Power Analysis and Differential Power Analysis, have been proposed to analyze encryption key data by measuring electric power consumption during the execution of the encryption and estimating generated intermediate data. These deciphering methods can be used to attack cryptographic modules implemented in both software and hardware.
As security solution against the above-described deciphering methods, non-patent reference 1 discloses a White-Box cryptography technology. FIG. 1 is a flowchart for explaining an example of the White-Box cryptography technology. Firstly, in this technology, encryption using fixed key data is described by a table. The expression of “encryption is described by a table” means that a relationship between input and output data in each conversion processing during the execution of the encryption is represented in a format of a conversion table. More specifically, the generated table is indicated by indexes representing inputs and elements representing outputs. In this description, it is assumed that an input is represented by an index and an output is represented by an element, in generating the table. For example, in encryption execution, an exclusive OR operation is executed on 8-bit input data X and 8-bit key data K, and the resulting 8-bit data is outputted as output data Y (S2). Here, when the key data has a fixed value, this is considered as fixed conversion of 8-bit input to 8-bit output. Based on the above, all conversion during the encryption are described in a conversion table (S4). Then, the resulting table is randomized by random numbers generated at random. More specifically, as one example, table conversion expressed by Y=Tab[X] (where X is input, Y is output, and Tab[ ] is an array indicated by the conversion table) is randomized using random numbers r1 and r2, to be conversion expressed by rY=Tab[X(+)r1](+)r2 (where (+) denotes an exclusive OR operation for each bit) (S6). The resulting random conversion is further described in a randomized table rTab[ ] (S8). The above randomizing is executed on all table conversion to generate the randomized table. Table conversion using the randomized table is herein called random encryption. The randomized encryption is implemented as a cryptographic module.
In the manner described as above, the input and output data in each table conversion are randomized by random numbers into values distinct from the actual intermediate values in encrypting the key data. Therefore, even if values in a register during the execution of the encryption are monitored, an attacker obtains only the above-described randomized intermediate values and fails to analyze the encryption key data. The non-patent document 1 discloses in detail a method of applying the above-described White-Box cryptography technology to Advanced Encryption Standard (AES) which is adopted as a next-generation cryptographic standard by the US government. In the white-box cryptography technology, mechanism of describing encryption by tables is important. In particular, it is crucial to generate conversion tables whose data amount is as small as possible.    [Non-Patent Reference 1] “White-Box Cryptography and an AES Implementation”; Stanley Chow, Philip Eisen, Harold Johnson, Paul C. van Oorschot; Selected Areas in Cryptography (LNCS2595), 2003, Springer-Verlag